package arithmetic.demo6;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * 题目：dp_跳跃游戏(2)
 */

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        // 创建dp
        int[] dp = new int[n];

        // 填表
        for(int i = 1 ; i < n; i++) {
            int minStep = 0x3f3f3f3f;
            // 寻找前面的最小步数
            for(int j = 0; j < i ; j++) {
                // 遍历前面的步数
                if(j + nums[j] >= i && dp[j] <= minStep ) {
                    dp[i] = dp[j] + 1;
                    minStep = dp[j];
                }
            }

        }


        return dp[n-1];
    }
}


/**
 * 层序遍历_跳跃游戏(2)
 */


class Solution1 {
    public int jump(int[] nums) {
        int n = nums.length;
        if(n == 1) return 0;
        int ret = 0;

        // 使用 left 和 right 来划分区域
        int left  = 0, right =  0;
        while(right < n - 1) {
            // 开始跳跃
            ret++;

            int index = 0;
            for(int i = left ; i <= right ; i++) {
                // 统计该区域所能到达的最大步数
                // 从当前位置出发所能达到的最大距离
                index = Math.max(index, nums[i] + i);
            }


            // 先定位左区间
            left = right + 1;
            // 更新右边界
            right = index;

        }



        return ret;
    }
}


/**
 * 线性多dp_最长湍流子数组
 */

class Solution2 {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        //    特判一下
        if(n == 0 || n == 1 ) return n;

        int count = 1;
        for(int j = 0; j < n - 1; j++) {
            if(arr[j] == arr[j + 1]) {
                count++;
            }
        }


        if(count == n) return 1;

        // 创建 dp 表
        int[] up = new int[n];
        int[] down = new int[n];

        // 初始化
        up[0] = down[0] = 1;

        // 填表
        for(int i = 1; i < n ; i++) {
            if (arr[i] - arr[i-1] > 0) {
                up[i] = down[i-1] + 1;
                // 1 就代表自己单干， 表示这个位置已经断了
                // 1 就代表从头开始
                down[i] = 1;
            }  else if(arr[i] - arr[i-1] < 0){
                down[i] = up[i - 1] + 1;
                up[i] = 1;
            } else {
                up[i] = down[i] = 1;
            }
        }

        // 寻找最长的子数组
        int ret = 0;
        for(int i = 0 ; i < n; i++) {
            ret = Math.max(ret, up[i]);
            ret = Math.max(ret, down[i]);
        }



        return ret;

    }
}

/**
 * 多状态dp_单词拆分
 */

class Solution3 {

    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        if(n == 1) {
            if(wordDict.contains(s.charAt(0) + "")) {
                return true;
            } else {
                return false;
            }
        }

        // 创建 dp 表
        boolean[] dp = new boolean[n + 1];
        // 初始化
        dp[0] = true;
        s = " " + s;

        // 填表
        for(int i = 1; i <= n ; i++) {

            // 判断前面
            for(int j = 1; j <= i; j++) {
                String str = s.substring(j,i + 1);
                // 判断能否状态转移
                if(  dp[j - 1] && wordDict.contains(str)) {
                    dp[i] = true;
                    break;
                }

            }
        }

        return dp[n];
    }
}


class Test {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        List<String> list = new ArrayList<>();
        list.add("aaaa");
        list.add("aaa");
        System.out.println(solution3.wordBreak("aaaaaaa", list));
    }
}